#include "abplayer.h"
#include <string.h>

namespace Connect5
{ 
    int ABPlayer::dirs_[8][2] = 
    {
        {-1, -1}, {-1, 0}, {-1, 1},
        {0, -1},           {0, 1},
        {1, -1}, {1, 0}, {1, 1}
    };
    int ABPlayer::base_ = 8; //计分基数
    int ABPlayer::black_score_5[6][6] = {0};

    ABPlayer::ABPlayer() : init_(false)
    {
        memset(board_, 0, sizeof(board_));
        int score = 1;
        for(int i=1; i<5; i++)
        {
            black_score_5[i][0] = score;
            black_score_5[0][i] = -score;
            score *= base_;
        }
        black_score_5[0][5] = min_score;
        black_score_5[5][0] = max_score;
    }

    ABPlayer::~ABPlayer()
    {
        release_step_link();
    }

    void ABPlayer::set_board(const Role (&board)[16][16])
    {
        memcpy(board_, board, sizeof(board));
        init_ = false;
    }

    void ABPlayer::set_board(int x, int y, Role r)
    {
        board_[x][y] = r;
        init_ = false;
    }

    void ABPlayer::think(int depth)
    {
        if(!init_)
        {
            int role_cnt = init_state();
            if(role_cnt < 2)
            {
                simple_think();
                return;
            }
        }

        role_ = white_ < black_ ? Role::WHITE : Role::BLACK;
        int score = 0;
        x_ = -1; y_ = -1;
        for(int i=1; i<=depth; i++)
        {
            depth_ = i;
            score = dfs(0, min_score, max_score);
            if(score == max_score)
            {
                break;
            }
        }
        printf("ABPlayer score:%d\n", score);
        //必输就任意走一步
        if(-1 == x_ && step_cnt_ > 0)
        {
            x_ = step_stack_[0][0];
            y_ = step_stack_[0][1];
        }
    }
    int ABPlayer::dfs(int depth, int low, int up)
    {
        if(depth == depth_ || current_black_score_== min_score || current_black_score_==max_score|| 0 == step_cnt_)
        {
            //无解：已到达指定深度或者已经赢/输了, 或者盘面满了无棋可走
            return  (depth & 0x1)^(role_ == Role::BLACK) ? current_black_score_ : -current_black_score_;
        }


        int current_black_score = current_black_score_; //用于还原current_black_score_;
        int current_score = min_score; //搜索过程中的当前得分
        auto current_role = (depth & 0x1)^(role_ == Role::BLACK) ? Role::BLACK : Role::WHITE;
        int child_low = -up, child_up = -low;
        auto cur_step_cnt = step_cnt_;
        int cur_step[2];
        for(int i = 0; i<step_cnt_; i++) 
        {
            auto & step = step_stack_[i];
            //goahead(p)
            board_[step[0]][step[1]] = current_role; //更新棋盘
            update_black_score(step[0], step[1]); //update current_black_score_
            auto & last_step = step_stack_[--step_cnt_];
            cur_step[0] = step[0]; step[0] = last_step[0]; //移除p
            cur_step[1] = step[1]; step[1] = last_step[1]; //移除p

            //新增next step nodes, 值考虑邻居节点，最多8个, 创建再栈上，再返回时可自动销毁
            int  ni = 0; //新增节点数
            int none_steps[8][2];
            for(int k=0; k<8; k++) //添加新增的next step
            {
                int ii = cur_step[0] + dirs_[k][0];
                if(ii<0 || ii>14)
                {
                    continue;
                }
                int jj = cur_step[1] + dirs_[k][1];
                if(jj<0 || jj>14) 
                {
                    continue;
                }
                nbr_map_[ii][jj]++;
                //首次发现空的邻接点, 则入链
                if(1 == nbr_map_[ii][jj] && Role::NONE == board_[ii][jj])
                {
                    auto & nstep = step_stack_[step_cnt_++];
                    nstep[0] = ii; nstep[1] = jj;
                }
                else
                {
                    auto & nstep = none_steps[ni++];
                    nstep[0] = ii; nstep[1] = jj;
                }
            }

            
            //recurse search
            int cur_child_score = dfs(depth+1, child_low, child_up);
            int temp_score = -cur_child_score;

            //rollback(p);
            board_[cur_step[0]][cur_step[1]] = Role::NONE;
            current_black_score_ = current_black_score;
            //恢复nbr_map_
            while(ni>0)
            {
                auto & nstep = none_steps[--ni];
                nbr_map_[nstep[0]][nstep[1]]--;    
            }
            while(step_cnt_ >= cur_step_cnt)
            {
                auto & nstep = step_stack_[--step_cnt_];
                nbr_map_[nstep[0]][nstep[1]]--;    
            }
            last_step[0] = step[0]; last_step[1]=step[1]; //恢复p
            step[0] = cur_step[0]; step[1]=cur_step[1]; //恢复p
            step_cnt_++; //恢复step_stack_

            //check
            if(temp_score > current_score) 
            {
                if(depth == 0)
                {
                    x_ = step[0]; y_= step[1]; //可能的最优解
                }
                current_score = temp_score;
            }

            if(current_score >= up)
            {
                //return current_role==Role::BLACK ?current_score: -current_score;
                return current_score;
            }

            //current_score < up => -current_score > -up            


            // no need
            //if(current_score <= low) //遍历完所有子分值，才能确定最终得分
            
            //更新child_up
            int current_min_child_score = -current_score;
            if(current_min_child_score < child_up)
            {
                child_up = current_min_child_score;
            }
            //child_up = -low, child_low = -up, low < up => child_up > child_low 
            //child_up = -current_score, -current_score > -up, -up = child_low => child_up>child_low
            //no need 
            // if(child_up <= child_low)
        }
        //if(current_score <= low) // no need just return: 必输或者被裁(父类被裁)
        return current_score;
    }


    int ABPlayer::init_state()
    {
        black_=0; white_ = 0; //用于判断当前(depth=0)角色
        release_step_link();
        memset(nbr_map_, 0, sizeof(nbr_map_));
        for(int i=0; i<15; i++)
        {
            for(int j=0; j<15; j++)
            {
                if(board_[i][j] == Role::NONE)
                {
                    continue;
                }
                if(board_[i][j] == Role::WHITE)
                {
                    white_++;     
                }
                else
                {
                    black_++;
                }
                //仅考虑当前棋子的邻居位置
                for(int k=0; k<8; k++)
                {
                    int ii = i + dirs_[k][0];
                    if(ii<0 || ii>14)
                    {
                        continue;
                    }
                    int jj = j+dirs_[k][1];
                    if(jj<0 || jj>14) 
                    {
                        continue;
                    }
                    nbr_map_[ii][jj]++;
                    //首次发现空的邻接点, 则入链
                    if(1 == nbr_map_[ii][jj] && Role::NONE == board_[ii][jj])
                    {
                        auto & nstep = step_stack_[step_cnt_++];
                        nstep[0] = ii; nstep[1] = jj;
                    }
                }
            }
        }
        current_black_score_ = black_score();
        init_ = true;
        return white_+black_;
    }    

    void ABPlayer::release_step_link()
    {
        step_cnt_ = 0;
    }
    void ABPlayer::simple_think()
    {
        for(int i=0; i<15; i++)
        {
            for(int j=0; j<15; j++)
            {
                if(Role::NONE != board_[i][j])
                {
                    x_ = i>7 ? i-1 : i+1;
                    y_ = j>7 ? j-1 : j+1;
                    return;
                }
            }
        }
        x_ = y_ = 7;
    }
    int ABPlayer::black_score() const
    {
        int score = 0, cur;
        int white, black;

        //将棋盘左上角视为原点(0行, 0列), 行r/x/i, 列c/y/j
        for(int i=0; i<15; i++)
        {
            for(int j=0; j<15; j++)
            {
                //横:以(i,j)开头的横向五元组(i,j) --> (i,j+4)
                //j+4 < 15 => j<11
                if(j<11)
                {
                    white = black = 0;
                    for(int k=j; k<j+5; k++)
                    {
                        if(board_[i][k] == Role::BLACK)
                        {
                            black++;
                        }
                        if(board_[i][k] == Role::WHITE)
                        {
                            white++;
                        }
                    }
                    cur = black_score_5[black][white];
                    if(cur == min_score || cur == max_score)
                    {
                        return cur;
                    }
                    score += cur;
                }
                
                if(i<11)
                {
                    //竖:以(i,j)开头的纵向五元组(i,j) --> (i+4,j)
                    //i+4 < 15 => i<11
                    white = black = 0;
                    for(int k=i; k<i+5; k++)
                    {
                        if(board_[k][j] == Role::BLACK)
                        {
                            black++;
                        }
                        if(board_[k][j] == Role::WHITE)
                        {
                            white++;
                        }
                    }
                    cur = black_score_5[black][white];
                    if(cur == min_score || cur == max_score)
                    {
                        return cur;
                    }
                    score += cur;

                    //斜:以(i,j)开头的斜向五元组(i,j) --> (i+4,j-4)
                    //i+4 < 15 => i<11, j-4 >= 0 => j>=4 => j>3
                    if(j>3)
                    {
                        white = black = 0;
                        for(int k=i; k<i+5; k++)
                        {
                            if(board_[k][j+i-k] == Role::BLACK)
                            {
                                black++;
                            }
                            if(board_[k][j+i-k] == Role::WHITE)
                            {
                                white++;
                            }
                        }
                        cur = black_score_5[black][white];
                        if(cur == min_score || cur == max_score)
                        {
                            return cur;
                        }
                        score += cur;
                        
                    }

                    //反斜:以(i,j)开头的反斜向五元组(i,j) --> (i+4,j+4)
                    //i+4 < 15 => i<11, j+4 <15 => j<11
                    if(j<11)
                    {
                        white = black = 0;
                        for(int k=i; k<i+5; k++)
                        {
                            if(board_[k][j+k-i] == Role::BLACK)
                            {
                                black++;
                            }
                            if(board_[k][j+i-k] == Role::WHITE)
                            {
                                white++;
                            }
                        }
                        cur = black_score_5[black][white];
                        if(cur == min_score || cur == max_score)
                        {
                            return cur;
                        }
                        score += cur;
                    }
                }
            }
        }
        return score;
    }

    void ABPlayer::update_black_score(int x, int y)
    {
        int s, e;
        int white, black;
        int cur;
        //行
        s = y-4 >= 0 ? y-4 : 0;
        e = y+4 < 15 ? y : 10;
        //初5
        white = 0; black = 0;
        for(int j=s; j<s+5; j++)
        {
            if(board_[x][j] == Role::WHITE)
            {
                white++;
            }
            else if(board_[x][j] == Role::BLACK)
            {
                black++;
            }
        
        }
        cur = black_score_5[black][white];
        if(cur == max_score || cur == min_score)
        {
            current_black_score_ = cur;
            return;
        }
        current_black_score_ += cur;
        if(board_[x][y] == Role::BLACK)
        {
            current_black_score_ -= black_score_5[black-1][white];
        }
        else
        {
            current_black_score_ -= black_score_5[black][white-1];
        }
        for(int j=s; j<e; j++)
        {
            if(board_[x][j] == Role::WHITE)
            {
                white--;
            }
            else if(board_[x][j] == Role::BLACK)
            {
                black--;
            }
            if(board_[x][j+5] == Role::WHITE)
            {
                white++;
            }
            else if(board_[x][j+5] == Role::BLACK)
            {
                black++;
            }
            cur = black_score_5[black][white];
            if(cur == max_score || cur == min_score)
            {
                current_black_score_ = cur;
                return;
            }
            current_black_score_ += cur;
            if(board_[x][y] == Role::BLACK)
            {
                current_black_score_ -= black_score_5[black-1][white];
            }
            else
            {
                current_black_score_ -= black_score_5[black][white-1];
            }
        }

        //列
        s = x-4 >= 0 ? x-4 : 0;
        e = x+4 < 15 ? x : 10;
        //初5
        white = 0; black = 0;
        for(int i=s; i<s+5; i++)
        {
            if(board_[i][y] == Role::WHITE)
            {
                white++;
            }
            else if(board_[i][y] == Role::BLACK)
            {
                black++;
            }
        
        }
        cur = black_score_5[black][white];
        if(cur == max_score || cur == min_score)
        {
            current_black_score_ = cur;
            return;
        }
        current_black_score_ += cur;
        if(board_[x][y] == Role::BLACK)
        {
            current_black_score_ -= black_score_5[black-1][white];
        }
        else
        {
            current_black_score_ -= black_score_5[black][white-1];
        }
        for(int i=s; i<e; i++)
        {
            if(board_[i][y] == Role::WHITE)
            {
                white--;
            }
            else if(board_[i][y] == Role::BLACK)
            {
                black--;
            }
            if(board_[i+5][y] == Role::WHITE)
            {
                white++;
            }
            else if(board_[i+5][y] == Role::BLACK)
            {
                black++;
            }
            cur = black_score_5[black][white];
            if(cur == max_score || cur == min_score)
            {
                current_black_score_ = cur;
                return;
            }
            current_black_score_ += cur;
            if(board_[x][y] == Role::BLACK)
            {
                current_black_score_ -= black_score_5[black-1][white];
            }
            else
            {
                current_black_score_ -= black_score_5[black][white-1];
            }
        }

        //左上
        s = x-4 >= 0 ? x-4 : 0; //for x
        if(y+s-x<0)
        {
            s = x-y;
        }
        e = x+4 < 15 ? x : 10;
        if(y+e-x + 4 > 14) 
        {
            e = x-y+10;
        }
        //初5
        white = 0; black = 0;
        for(int i=s; i<s+5; i++)
        {
            if(board_[i][y+i-x] == Role::WHITE)
            {
                white++;
            }
            else if(board_[i][y+i-x] == Role::BLACK)
            {
                black++;
            }

        }
        cur = black_score_5[black][white];
        if(cur == max_score || cur == min_score)
        {
            current_black_score_ = cur;
            return;
        }
        current_black_score_ += cur;
        if(board_[x][y] == Role::BLACK)
        {
            current_black_score_ -= black_score_5[black-1][white];
        }
        else
        {
            current_black_score_ -= black_score_5[black][white-1];
        }
        for(int i=s; i<e; i++)
        {
            if(board_[i][y+i-x] == Role::WHITE)
            {
                white--;
            }
            else if(board_[i][y+i-x] == Role::BLACK)
            {
                black--;
            }
            if(board_[i+5][y+i+5-x] == Role::WHITE)
            {
                white++;
            }
            else if(board_[i+5][y+i+5-x] == Role::BLACK)
            {
                black++;
            }

        }
        cur = black_score_5[black][white];
        if(cur == max_score || cur == min_score)
        {
            current_black_score_ = cur;
            return;
        }
        current_black_score_ += cur;
        if(board_[x][y] == Role::BLACK)
        {
            current_black_score_ -= black_score_5[black-1][white];
        }
        else
        {
            current_black_score_ -= black_score_5[black][white-1];
        }

        //右上
        s =  x-4 >= 0 ? x-4 : 0;  //for x
        if(y+x-s>14)
        {
            s = y+x-14;
        }
        e = x+4 < 15 ? x : 10;
        if(y+x-e-4 < 0)
        {
            e = x+y-4;
        }
        //初5
        white = 0; black = 0;
        for(int i=s; i<s+5; i++)
        {
            if(board_[i][y+x-i] == Role::WHITE)
            {
                white++;
            }
            else if(board_[i][y+x-i] == Role::BLACK)
            {
                black++;
            }
        
        }
        cur = black_score_5[black][white];
        if(cur == max_score || cur == min_score)
        {
            current_black_score_ = cur;
            return;
        }
        current_black_score_ += cur;
        if(board_[x][y] == Role::BLACK)
        {
            current_black_score_ -= black_score_5[black-1][white];
        }
        else
        {
            current_black_score_ -= black_score_5[black][white-1];
        }
        for(int i=s; i<e; i++)
        {
            if(board_[i][y+x-i] == Role::WHITE)
            {
                white--;
            }
            else if(board_[i][y+x-i] == Role::BLACK)
            {
                black--;
            }
            if(board_[i+5][y+x-i-5] == Role::WHITE)
            {
                white++;
            }
            else if(board_[i+5][y+x-i-5] == Role::BLACK)
            {
                black++;
            }
            cur = black_score_5[black][white];
            if(cur == max_score || cur == min_score)
            {
                current_black_score_ = cur;
                return;
            }
            current_black_score_ += cur;
            if(board_[x][y] == Role::BLACK)
            {
                current_black_score_ -= black_score_5[black-1][white];
            }
            else
            {
                current_black_score_ -= black_score_5[black][white-1];
            }
        }
    }
    void ABPlayer::get_next(int &x, int &y)
    {
        x = x_;
        y = y_;
    }
    void ABPlayer::goahead(int x, int y)
    {
        if(!init_)
        {
            init_state();
        }
        Role role;
        if(black_ > white_) 
        {
            role = Role::WHITE;
            white_++;
        }
        else
        {
            role = Role::BLACK;
            black_++;
        }
        board_[x][y] = role; //更新棋盘
        update_black_score(x, y); //update current_black_score_
        for(int k=0; k<8; k++) //更新nbr_map_
        {
            int ii = x + dirs_[k][0];
            if(ii<0 || ii>14)
            {
                continue;
            }
            int jj = y+dirs_[k][1];
            if(jj<0 || jj>14)
            {
                continue;
            }
            nbr_map_[ii][jj]++;
            //首次发现空的邻接点, 则入链
            if(1 == nbr_map_[ii][jj] && Role::NONE == board_[ii][jj])
            {
                auto & step = step_stack_[step_cnt_++];
                step[0] = ii; step[1] = jj;
            }
        }
        if(nbr_map_[x][y] > 0) //当前节点已加入链表
        {
            //从链表中删除当前节点
            for(int i = 0; i<step_cnt_; i++) 
            {
                auto & step = step_stack_[i];
                if(step[0] == x && step[1] == y)
                {
                    auto last_step = step_stack_[--step_cnt_];
                    step[0] = last_step[0]; step[1] = last_step[1];
                    break;
                }

            }
        }
    }

    void ABPlayer::rollback(int x, int y)
    {
        if(!init_)
        {
            init_state();
        }
        auto score = current_black_score_;
        update_black_score(x, y);
        //current_black_score_ - score = score - rbk =>
        //rbk = score*2 - current_black_score_    
        current_black_score_ = score*2 - current_black_score_;
        if(white_ < black_)
        {
            black_--;
        }
        else
        {
            white_--;
        }
        board_[x][y] = Role::NONE;
        for(int k=0; k<8; k++) //更新nbr_map_
        {
            int ii = x + dirs_[k][0];
            if(ii<0 || ii>14)
            {
                continue;
            }
            int jj = y+dirs_[k][1];
            if(jj<0 || jj>14)
            {
                continue;
            }
            nbr_map_[ii][jj]--;
            //发现0邻居空点, 则出链
            if(0 == nbr_map_[ii][jj] && Role::NONE == board_[ii][jj])
            {
                for(int i = 0; i<step_cnt_; i++) 
                {
                    auto & step = step_stack_[i];
                    if(step[0] == ii && step[1] == jj)
                    {
                        auto last_step = step_stack_[--step_cnt_];
                        step[0] = last_step[0]; step[1] = last_step[1];
                        break;
                    }

                }
            }
        }
        if(nbr_map_[x][y]>0) //当前节点应该加入链表
        {
            auto & step = step_stack_[step_cnt_++];
            step[0] = x; step[1] = y;
        }
    }
    void ABPlayer::clear()
    {
        release_step_link();
        memset(board_, 0, sizeof(board_));
        memset(nbr_map_, 0, sizeof(nbr_map_));
        init_ = false;
    }

    void ABPlayer::show()
    {
        int step_map[16][16] = {0};
        for(int i = 0; i<step_cnt_; i++) 
        {
            auto & step = step_stack_[i];
            step_map[step[0]][step[1]] = 1;
        }
  	    puts("  A B C D E F G H I J K L M N O");
        for(int i=0; i<15; i++)
        {
  		    printf("%c ",i+97);
            for(int j=0; j<15; j++)
            {
                auto role = board_[i][j];
                if(role == Role::BLACK)
                {
                    printf("X ");
                }
                else if(role == Role::WHITE)
                {
                    printf("O ");
                }
                else
                {
                    if(step_map[i][j] == 1)
                    {
                        printf("\033[1;31m.\033[0m ");
                    }
                    else
                    {
                        printf(". ");
                    }
                }
            }
    	    putchar('\n');
        }
    }

} //namespace Connect5
